const arr = [3, 6, 1, 1, 2, 4, 8, 9, 7, 8, 5, 6, 3, 2, 5, 6, 9, 8, 7, 8, 9]
function quickSort(arr) {
    if (arr.length <= 1) return arr
    const p = arr[0]
    const left = []
    const right = []
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] < p) {
            left.push(arr[i])
        } else {
            right.push(arr[i])
        }
    }
    return quickSort(left).concat(p, quickSort(right))
}
console.log(quickSort(arr))

/**
 * 时间复杂度T(n) = O(n)
*/